package 一些笔试真题;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-10-06
 * Time: 12:03
 */

/*
    合并二叉树
 */
class node{
    int val = 0;
    node left = null;
    node right = null;
}

public class guazi_3 {
    private static void createTree(Scanner scanner, node[] array, int n){
        for(int i = 1; i <= n; i++){
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            int val = scanner.nextInt();
            if(left != 0){
                array[i].left = array[left];
            }
            if(right != 0){
                array[i].right = array[right];
            }
            array[i].val = val;
        }
    }

    private static node merge(node root1, node root2){
        if(root1 != null && root2 != null){
            root1.left = merge(root1.left, root2.left);
            root1.right = merge(root1.right, root2.right);
            root1.val = root1.val + root2.val;
            return root1;
        }
        return (root1 == null ? root2 : root1);
    }

    private static void BFS(node root){
        Queue<node> queue = new LinkedList<>();
        if(root != null){
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            node cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        node[] array1 = new node[n + 1];
        node[] array2 = new node[m + 1];
        for(int i = 0; i <= n; i++){
            array1[i] = new node();
        }
        for(int i = 0; i <= m; i++){
            array2[i] = new node();
        }
        createTree(scanner, array1, n);
        createTree(scanner, array2, m);
        node root1 = null;
        node root2 = null;
        if(array1.length > 1){
            root1 = array1[1];
        }
        if(array2.length > 1){
            root2 = array2[1];
        }
        node root = merge(root1, root2);
        BFS(root);
    }
}
